// 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

// 你可以认为每种硬币的数量是无限的。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/coin-change
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

// 第15超时

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(coins.size()<1){
            return 0;
        }
        int res = amount +1;
        int d =0;
        dfs(coins,amount,d,res);
        if(res==amount+1){
            res = -1;
        }
        return res;
    }
    void dfs(vector<int>& coins,int& amount,int d,int& res){
        if(amount<0){
            return;
        }
        if(amount==0){
            res = min(res,d);
            return;
        }
        for(int i=0;i<coins.size();i++){
            int temp = amount - coins[i];
            if(temp<0){
                return;
            }
            d++;
            dfs(coins,temp,d,res);
            d--;
        }
    }
};